2023 NepCTF

Van1sh 比赛小屋 Write Up
创建时间:
字数:8.3k 阅读:
  1. random_RSA
  2. bombe-crib
  3. bombe-Rejewski
  4. recover
  5. SecureAgg
  6. simple_des

周末去 NepCTF 玩了下，原本还想尝试一下其他方向的题目的，结果还是只会做密码学方向的题。太菜啦！！！不过这场比赛是个人赛，做完题目后看了一下榜，发现只要单方向 ak 了的话排名都不差，说明各个方向的题目难度设计和题量是比较合理的，真不戳~

![image-20230814130017620](./2023 NepCTF.assets/image-20230814130017620.png)

random_RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from gmpy2 import next_prime, invert as inverse_mod
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from random import getrandbits
from math import lcm
from sys import exit
flag = "1234"
global_bits = 1024

BANNER = rb"""
.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.
| N.--.  | E.--.  | P.--.  | C.--.  | T.--.  | F.--.  | H.--.  | A.--.  | P.--.  | P.--.  | Y.--.  |
|  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  (\/)  |
|  :\/:  |  :\/:  |  ()()  |  (__)  |  :\/:  |  (__)  |  :\/:  |  ()()  |  :\/:  |  :\/:  |  :\/:  |
|  '--'n |  '--'e |  '--'p |  '--'c | '--'t  |  '--'f |  '--'h |  '--'a |  '--'p |  '--'p |  '--'y |
`--------`--------`--------`--------'--------`--------`--------`--------`--------`--------`--------`
"""

def generate_prime(bits: int):
    p = (getrandbits(bits - 32) << 32)
    return next_prime(p)


def generate_private_key(bits: int):
    p, q = generate_prime(bits), generate_prime(bits)
    n, phi = p * q, lcm(p-1, q - 1)

    d = inverse_mod(0x10001, phi)
    privateKey = RSA.construct((int(n), int(0x10001), int(d), int(p), int(q)))
    return privateKey, p > q


if __name__ == "__main__":
    print(BANNER.decode())
    print("Welcome to the world of random RSA.")
    print("Please make your choice.")
    for _ in range(8):
        choice = input()

        if choice == '1':
            p, q = generate_prime(global_bits), generate_prime(global_bits)
            N = p*q
            d = generate_prime(global_bits-32)
            e = inverse_mod(d, (p * p - 1) * (q * q - 1))
            print(f"{int(N)}")
            print(f"{int(e)}")

        elif choice == '2':
            privateKey, signal = generate_private_key(global_bits)
            Cipher = PKCS1_v1_5.new(privateKey)
            c = (Cipher.encrypt(flag.encode()))
            print(c)
            exit()

        else:
            exit()

题目内容是比较简单的，基于 RSA 的变体，这里的 $n$ 是 2048 比特的，$d$ 只有 992 比特，$e \cdot d \equiv 1 \pmod{(p^2-1)\cdot (q^2-1)}$ ，手里头刚好有一篇论文 《Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits》不过这里还要求 $|p-q|$ 比较小。但是论文里头提了一嘴

![image-20230814094241576](./2023 NepCTF.assets/image-20230814094241576.png)

所以我们直接找 $\frac{e}{N^2-\frac{9}{4}N +1}$ 的连分数就能恢复 $d$，从而恢复 $p,q$ 了。注意到这里的 $p,q,d$ 的高 992 位都是由 getrandbits 生成的随机数。一共 8 次交互机会，所以能有 $992/327+960/32=644$ 个 32 字节的随机数，思路来了：恢复所有的 $p,q,d$ ，恢复一个 MT19937 的状态，然后直接生成后续的 *p,q,d** 就能解密了。

需要注意的是我们虽然能够计算出 $p,q$ ，但不能保证 $p$ 就是原来的 $p$，可能顺序反了，因此还需要组合一下。

这里首先通过交互，前 7 次拿公钥对，最后一次拿密文。然后连分数来一下子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#! sagemath
from gmpy2 import iroot

def attack(N,e):
    convergents = continued_fraction(ZZ(e) / ZZ(int(N^2-9/4*N+1))).convergents()
    for c in convergents:
        k = c.numerator()
        d = c.denominator()
        if pow(pow(2, e, N), d, N) == 2:
            phi = (e * d - 1) // k #(p^2-1)*(q^2-1) = n^2+1-p^2-q^2
            p_a_q = iroot(N^2+1-phi+2*N,2)[0]
            p_s_q = iroot(N^2+1-phi-2*N,2)[0]
            p = (p_a_q - p_s_q)//2
            q = N//p
            print("[+]")
            return int(p),int(q),int(d)

def chu(a):
    tmp = []
    while a != 0:
        tmp.append(a%2**32)
        a >>= 32
    return tmp

N = [...]	
E = [...]
P = []
D = []
for n,e in zip(N,E):
    p,q,d = attack(n,e)
    P.append(chu(p>>32))
    P.append(chu(q>>32))
    D.append(chu(d>>32))

然后调一下 MT19937 的板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#! python3
import random
from gmpy2 import next_prime, invert as inverse_mod
from gmpy2 import mpz
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from random import getrandbits
from math import lcm
import itertools

c = b'-#\xa6<\x05\x91.dx\x1dp\xb3\xaa6\xaa\xe5\x87\xb6\xda\\\xc4\x02\x89\xd6]\xa1\x08\xf5y\x8b\xfd\x8c0\xaaU]\xca\x1dw\xf6,\xa2\xf1\xc0[0cU\xb6\xdd\x7f\xdd\xa4\xab\x033FLGR\xe8\x99\\\tw\xa6j\x1d\x8b\xf8[\xa55\xbdx\x7f\x14\xd6\xf6\xc9*;\xf2\\\x0eN\xe0\x1fJ0\xa9\xc2\xbd]\x0cFM\xd0|\x0e\x8dQ.\xd3y\x0f+\xf3\xd1h>\x0e\x9b\xa2>\xa2\xcd\xbd\xd7\x14O\xf8$rF\r#o\x94\x87ys_\xe0\xba\x97\x9bo\xa1S\x07\'\x8au\xfbg\xf1\x99\xe4\xf0{\xef`\xbfZ\xe1a\x13\x1d\x91\x9b\xb1cJ\x7f \xec}\xeaS j,\xeb\x9d\x95\xf5a\xab\x02\xe6\xf2\x06f\x9eF\x96:\xba};\xd9\xfc\xdb"\xb5G>\xe1<\xae1\x17x\xbeN\x05\xab^\x96\xb7\x9d\xb6lS fo\x95\xb8\x19\xa4\xf8\r,V\x8e\xa1\xcf\xcf\x82\x9a\xbd~\xbd\xfb\xb3\xe2\xd83\xf7\x0c\x01\x9bW:\x92lj\x85\x92\x89Gsw\xcc'

for i in itertools.product([0,1],repeat = 7):
    N = []
    index = 0
    for each in i:
        N+=PP[index][each]
        N+=PP[index][1-each]
        N+=D[index]
        index+=1
    N = [int(n) for n in N]

    mtb = MT19937Recover()
    try:
        r2 = mtb.go_on(N)
    except Exception as e:
        continue
    p, q = generate_prime(1024), generate_prime(1024)
    n, phi = p * q, lcm(p-1, q - 1)

    d = inverse_mod(0x10001, phi)
    privateKey = RSA.construct((int(n), int(0x10001), int(d), int(p), int(q)))
    Cipher = PKCS1_v1_5.new(privateKey)
    flag = (Cipher.decrypt(c,'\x00'))
    print(flag)
    exit()

b'NepCTF{c4e4356067fb3bedc53dde7af59beb1c}'

bombe-crib

题目说明：

面对每天六点德军铺天盖地的天气预报，你突然想到了怎么确定关键信息的位置。

注：enigma机可使用pyenigma项目，但源项目有问题，可修改后使用cyberchef对拍。

是一个恩格玛机相关的题目，代码文件太多，这里只放一下交互的 handle 部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from pwn import *
from pwnlib.util.iters import mbruteforce
from hashlib import sha256
sh = remote("nepctf.1cepeak.cn",31211)

context.log_level = 'debug'
def proof_of_work(sh):
    sh.recvuntil("XXXX+")
    suffix = sh.recvuntil(')').decode("utf8")[:-1]
    log.success(suffix)
    sh.recvuntil("== ")
    cipher = sh.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==  cipher, string.ascii_letters + string.digits, length=4, method='fixed')
    sh.sendlineafter("[+] Plz tell me XXXX: ", proof)

def check(pos):
    for index in range(len(flag)):
        for each in s:
            if each[pos%52] == flag[index]:
                return False
        pos+=1
    return True

proof_of_work(sh)
flag = "WETTERBERICHT"


for _ in range(10):
    s = []
    for _ in range(20):
        s.append(sh.recvuntil("\n")[:-1].decode())
    print(s)
    for pos in range(len(s[0])):
        if check(pos):
            sh.recvuntil("[-] ")
            sh.sendline(str(pos))
            break
sh.interactive()

看一下题目流程，

  1. 先生成了一段随机字符串 other
  2. 指定一个位置 pos ，在该位置插入已知明文 WETTERBERICHT，组成 text
  3. 指定了恩格玛机加密所需要的转子： dayrotors
  4. 对 text 进行二十次加密，每次使用不同的 tmpkey 和 plugin

所以我们就是需要根据 text 的二十个密文来确定 WETTERBERICHT 所在的位置。

在此前我对恩格玛机也是一点都不了解的，在查相关资料的时候，看见了这么一句话

![image-20230814101223587](./2023 NepCTF.assets/image-20230814101223587.png)

明文不可能加密回自己本身，思路来了：只需要判断从哪个位置开始，二十个密文的子串和 WETTERBERICHT 的重合率为 0 即可。

举个例子就是，假设 pos=0，那么二十个密文的第一个字符都不会是 W，第二个字符都不会是 E。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from pwn import *
from pwnlib.util.iters import mbruteforce
from hashlib import sha256
sh = remote("nepctf.1cepeak.cn",31211)

context.log_level = 'debug'
def proof_of_work(sh):
    sh.recvuntil("XXXX+")
    suffix = sh.recvuntil(')').decode("utf8")[:-1]
    log.success(suffix)
    sh.recvuntil("== ")
    cipher = sh.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==  cipher, string.ascii_letters + string.digits, length=4, method='fixed')
    sh.sendlineafter("[+] Plz tell me XXXX: ", proof)

def check(pos):
	for index in range(len(flag)):
		for each in s:
			if each[pos%52] == flag[index]:
				return False
		pos+=1
	return True

proof_of_work(sh)
flag = "WETTERBERICHT"


for _ in range(10):
	s = []
	for _ in range(20):
		s.append(sh.recvuntil("\n")[:-1].decode())
	print(s)
	for pos in range(len(s[0])):
		if check(pos):
			sh.recvuntil("[-] ")
			sh.sendline(str(pos))
			break
sh.interactive()

bombe-Rejewski

题目说明：

德军目前使用日密钥加密临时密钥两次的工作模式，相信你一定可以发现其中的端倪！

注：enigma机可使用pyenigma项目，但源项目有问题，可修改后使用cyberchef对拍。

注：本题update了以下部分

  1. 修改了积分逻辑，统计密钥恢复正确的正确次数；
  2. 修改了挑战次数，提升一次打通的概率；
  3. 增加了日接线板，现在无法使用爆破的方式直接破拆；

还是看到 handle 部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def handle(self):
    signal.alarm(5)
    if not self.proof_of_work():
        self.send(b'[!] Wrong!')
        return
    score=0
    r1,r2,r3=myrotors[:3]    
    for _ in range(20):
        s=product(ascii_uppercase,repeat=3)
        daykey="".join(choice(list(s)))
        k1=list(ascii_uppercase)
        k2=list(ascii_uppercase)
        k3=list(ascii_uppercase)
        shuffle(k1)
        shuffle(k2)
        shuffle(k3)
        tmpkeys=[x+y+z for x,y,z in zip(k1,k2,k3)]

        for key in  tmpkeys:
            myEnigma=enigma.Enigma(myReflector,r1,r2,r3,daykey)
            c1=myEnigma.encipher(key)
            c2=myEnigma.encipher(key)
            self.send((c1+c2).encode())
        self.send(b"now gave me the daykey:") 
        ans=self.recv()
        if daykey.encode()==(ans[:3]):
            score+=1
    
    if score>=10:
        self.send(b'your score is %d,here is your flag'%score)
        self.send(flag)
    else :
        self.send(b'sorry,your score is %d, plz try again'%score)

看一下题目流程，

  1. 指定一个 3 字节的 daykey
  2. 生成三个打乱的字母表 k1,k2,k3
  3. 将每个字母表相同位置的字母取出来组合，生成 26 个 3 字节的随机字符串 tmpkeys
  4. 对每个随机字符串加密两次，输出密文。（根据恩格玛机的加密特性，本质上是加密了一串重复的字符串）

没有思路，找巨人的肩膀，根据 Rejewski，

搜到了论文 https://people.cs.uchicago.edu/~davidcash/284-autumn-19/02-permutations-and-enigma.pdf # Rejewski’s Theorem and Attack

在github上搜到了项目 https://github.com/NationalSecurityAgency/enigma-simulator/tree/master

简单读了下论文，了解了一下攻击流程。然后就可以跟着项目里的 MasterEnigmaCracker.ipynb 做了。不过需要调一下恩格玛机的参数。要把 rotor 和 Reflector 调成题目里的。

在 enigma-simulator-master/components.py 中设置

1
2
3
4
5
6
7
8
ROTOR_WIRINGS = {
    'I': {'forward': 'UHQAOFBEPIKZSXNCWLGJMVRYDT',
          'backward':'DGPYHFSBJTKRUOEICWMZAVQNXL'},
    'II':{'forward':'RIKHFBUJDNCGWSMZVXEQATOLYP',
          'backward':'UFKISELDBHCXOJWZTANVGQMRYP'},
    'III':{'forward':'ENQXUJSIVGOMRLHYCDKTPWAFZB',
           'backward':'WZQRAXJOHFSNLBKUCMGTEIVDPY'},
}

其中 backword 的计算方式在题目给的 pyenigma/rotor 中有

1
2
3
4
5
6
7
8
if wiring != None:
    self.wiring = wiring
else:
    self.wiring="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
self.rwiring = ["0"] * 26
# 根据 forward 计算 backword
for i in range(0, len(self.wiring)):
    self.rwiring[ord(self.wiring[i]) - ord('A')]= chr(ord('A') + i)

然后还要在 component 中调一下 reflector

1
2
3
4
5
6
class Reflector:
    '''
    This class defines the reflector for the Engima machine.
    '''
    def __init__(self):
        self.wiring = {'A': 'W', 'B': 'O', 'C': 'E', 'D': 'H', 'E': 'C', 'F': 'K', 'G': 'Y', 'H': 'D', 'I': 'M', 'J': 'T', 'K': 'F', 'L': 'R', 'M': 'I', 'N': 'Q', 'O': 'B', 'P': 'Z', 'Q': 'N', 'R': 'L', 'S': 'V', 'T': 'J', 'U': 'X', 'V': 'S', 'W': 'A', 'X': 'U', 'Y': 'G', 'Z': 'P'}

另外在调 rejewski.py 中的 make_chain_length_dict() 函数生成字典的时候，根据直接把 rotors 的顺序定死 

1
2
3
for key in tqdm(keys):
    # For rotor combination in rotors.
    for order in (['I', 'II', 'III'],):

因为题目取得就是前三个转子 r1,r2,r3=myrotors[:3]

另外可能会出现多解的情况，我们无法判断，随便传一个就好；也有可能无解，那就随便猜一个。剩下的全靠运气了。我这里运气不错，第二次就成功了。

attack.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import machine as m


def generate_permutation_dicts(message_encrypts):
    '''
    Outputs AD, BE, and CF dictionaries generated from a series of double message key encryptions. 
    
    Params: message_encrypts = an iterator/list containing a double message key encryptions. 
    '''
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    AD = {letter:None for letter in alphabet}
    BE = {letter:None for letter in alphabet}
    CF = {letter:None for letter in alphabet}
    for m in message_encrypts:
         if any(AD[i] is None for i in AD) or any(BE[i] is None for i in BE) or any(CF[i] is None for i in CF):
                AD[m[0]] = m[3] if AD[m[0]] is None else AD[m[0]]
                BE[m[1]] = m[4] if BE[m[1]] is None else BE[m[1]]
                CF[m[2]] = m[5] if CF[m[2]] is None else CF[m[2]]
    return AD, BE, CF


def make_chains_from_permutation_dict(permutation_dict):
    '''
    Given a dictionary linking the first and fourth (or second and fifth or third and sixth) 
    letter combinations from the message keys, generate the length of chains (i.e. cycles of letters) 
    found in the dictionary.
    '''
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    chains = []
    while len(alphabet) > 0:
        next_chain = permutation_dict[alphabet[0]]
        next_letter = permutation_dict[next_chain[0]]
        # must remove the first two letters in the chain.
        alphabet = alphabet.replace(alphabet[0], '')
        alphabet = alphabet.replace(next_chain, '')
        while next_letter != next_chain[0]:
            next_chain += next_letter
            alphabet = alphabet.replace(next_letter, '')
            next_letter = permutation_dict[next_letter]
        chains.append(next_chain)
        alphabet.replace(next_letter, '')
    return chains

# Generate the indicies for your chains based on the permutation dictionaries. 
def generate_chain_index(chains):
    '''
    Given a list of chains for the AD, BE, and CF pairs, find their lengths and put them in a digestable form for indexing.

    MAJOR ASSUMPTION: these chains will come directly from my code, so they will be in the order AD, BE, CF.
    '''
    chain_index = 'AD:'
    for i, chain_list in enumerate(chains):
        if i == 1:
            chain_index = chain_index + ' BE:'
        elif i == 2:
            chain_index = chain_index + ' CF:'
        # Sort the chains to make sure the number is unique.
        chain_list.sort(key=lambda x: len(x))
        for c in chain_list:
            chain_index = chain_index + str(len(c))
    return chain_index
import pickle

def attack(s):
    e = m.Enigma()
    message_key_encrypts = s
    AD, BE, CF = generate_permutation_dicts(message_key_encrypts)
    AD_chains = make_chains_from_permutation_dict(AD)
    BE_chains = make_chains_from_permutation_dict(BE)
    CF_chains = make_chains_from_permutation_dict(CF)
    index = generate_chain_index([AD_chains, BE_chains, CF_chains])
    chains_dict = pickle.load(open('chains.pickle', 'rb'))
    s = (chains_dict[index])
    for each in s:
        return(''.join(i for i in each[0]))

inter.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import signal
import string
import random
from string import ascii_uppercase
from random import shuffle,choice
import os

from itertools import product
from pwn import *
from pwnlib.util.iters import mbruteforce

from hashlib import sha256
sh = remote("nepctf.1cepeak.cn",32483)
context.log_level = 'debug'

def proof_of_work(sh):
    sh.recvuntil("XXXX+")
    suffix = sh.recvuntil(')').decode("utf8")[:-1]
    log.success(suffix)
    sh.recvuntil("== ")
    cipher = sh.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==  cipher, string.ascii_letters + string.digits, length=4, method='fixed')
    sh.sendlineafter("[+] Plz tell me XXXX: ", proof)

proof_of_work(sh)

from attack import attack

for _ in range(30):
    s = sh.recvuntil("daykey:").split("\n")
    s = s[:-1]
    try:
        ans = attack(s)
    except:
        ans = 'AAA'
    sh.recvuntil("[-] ")
    sh.sendline(ans)
sh.interactive()

recover

题目描述：

小A发现一段纯P盒加密的密文，但等待他还原的其实是……？

（flag格式为flag{纯小写字母}，对应变量本身即包含flag{}结构）

flag变量给出了最终提交内容的具体约束，具体格式为flag{xxx}中间为18个小写字母，约束为对含有“flag{}”整体的约束。readable是可读，不只是printable可打印。请各位师傅自行估算复杂度，正解基于python的爆破时间在5min左右，请观察加密部件特征，降低复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
from math import ceil
from hashlib import md5

from Crypto.Util.number import *

from secret import key, flag


def MD5(x): return md5(x).hexdigest()


assert (len(flag) == 58)
assert (len(key) == 24)

P = [[0, 2, 3, 4, 5, 6],
     [1, 4],
     [0, 3],
     [0, 3, 4, 5],
     [0, 1, 2, 3, 4, 7],
     [2, 3, 4, 5, 6],
     [0, 1, 2, 3],
     [1, 2, 3, 4, 5, 7],
     [8, 12, 13, 14],
     [8, 11, 12, 13, 15],
     [9, 12, 15],
     [11, 13, 15],
     [8, 9, 10, 12, 13, 15],
     [8, 9],
     [11, 13, 14],
     [10],
     [16, 19, 20],
     [16, 18, 19, 20, 21],
     [16, 17, 18, 19],
     [17, 18, 20, 22, 23],
     [17, 19, 23],
     [17, 18, 20, 21, 23],
     [16, 18, 20, 21, 22, 23],
     [16, 17, 18, 20, 21, 22, 23],
     [25, 26, 29, 31],
     [25, 26],
     [26, 28, 30],
     [27, 28, 29, 30, 31],
     [25, 29],
     [25, 26, 30, 31],
     [28, 29, 30, 31],
     [24, 26, 29, 31],
     [35, 36, 39],
     [33, 35, 38],
     [33, 35, 37, 39],
     [32, 33, 34, 35, 37, 38],
     [32, 33, 34, 35, 37, 39],
     [35, 38],
     [33, 34, 38, 39],
     [33, 34, 39],
     [41, 42, 43, 44, 47],
     [40, 41, 42, 45, 47],
     [41, 42, 45, 47],
     [40, 43, 44, 46],
     [41, 46, 47],
     [41, 42, 43, 44, 46, 47],
     [41, 42, 44, 45],
     [40, 41, 42, 45, 46],
     [48, 50, 51, 52, 53, 54, 55],
     [48, 49, 50, 52, 53, 54, 55],
     [49, 55],
     [48, 49, 50, 51, 52, 54],
     [52, 53],
     [48, 49, 53, 54, 55],
     [48, 49, 52, 55],
     [48, 49, 51, 52, 55],
     [58, 59],
     [56, 61, 63],
     [57, 63],
     [56, 59, 60],
     [61, 63],
     [57, 58, 61, 62, 63],
     [57, 58],
     [60, 62]]


def enc(v, keys, le):
    t = v
    for i in keys:
        q = []
        for j in P:
            tmp = 0
            for k in j:
                tmp ^= t[k]
            q.append(tmp)
        t = [int(q[j]) ^ int(i[j]) for j in range(le)]
    return t


keys = []
for i in range(len(key)//8):
    l = bytes_to_long(key[i*8:i*8+8])
    m = bin(l)[2:].zfill(8*8)
    keys.append([int(i) for i in m])

fb = bin(bytes_to_long(flag))[2:].zfill(ceil(len(flag)/8)*8*8)

ciphertext = ""
for i in range(0, len(fb), 64):
    t = enc([int(j) for j in fb[i:i+64]], keys, 64)
    ciphertext += "".join([str(j) for j in t])

print(ciphertext)


"""
11101100100000110101100101100001100111011100100111000000010110000110011011000100110101110111010000100100001100010011001100010100101000110001011101000000100010101000000110000110011110001101110110110111000000100010011011011011101011101000000000100010000101001110100101011000001110010000000000100110001101110011111010001100101101111010101111101110100110101010011010011010101110100001001101100110010000010000011100100101111010010000011001000110000100110111100010101011000100100111010000101010110110001010110101111111
"""

题目流程，，不总结了，一看全是线性运算，思路来了：上 z3，加密照抄

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
from z3 import *


P = [[0, 2, 3, 4, 5, 6],
     [1, 4],
     [0, 3],
     [0, 3, 4, 5],
     [0, 1, 2, 3, 4, 7],
     [2, 3, 4, 5, 6],
     [0, 1, 2, 3],
     [1, 2, 3, 4, 5, 7],
     [8, 12, 13, 14],
     [8, 11, 12, 13, 15],
     [9, 12, 15],
     [11, 13, 15],
     [8, 9, 10, 12, 13, 15],
     [8, 9],
     [11, 13, 14],
     [10],
     [16, 19, 20],
     [16, 18, 19, 20, 21],
     [16, 17, 18, 19],
     [17, 18, 20, 22, 23],
     [17, 19, 23],
     [17, 18, 20, 21, 23],
     [16, 18, 20, 21, 22, 23],
     [16, 17, 18, 20, 21, 22, 23],
     [25, 26, 29, 31],
     [25, 26],
     [26, 28, 30],
     [27, 28, 29, 30, 31],
     [25, 29],
     [25, 26, 30, 31],
     [28, 29, 30, 31],
     [24, 26, 29, 31],
     [35, 36, 39],
     [33, 35, 38],
     [33, 35, 37, 39],
     [32, 33, 34, 35, 37, 38],
     [32, 33, 34, 35, 37, 39],
     [35, 38],
     [33, 34, 38, 39],
     [33, 34, 39],
     [41, 42, 43, 44, 47],
     [40, 41, 42, 45, 47],
     [41, 42, 45, 47],
     [40, 43, 44, 46],
     [41, 46, 47],
     [41, 42, 43, 44, 46, 47],
     [41, 42, 44, 45],
     [40, 41, 42, 45, 46],
     [48, 50, 51, 52, 53, 54, 55],
     [48, 49, 50, 52, 53, 54, 55],
     [49, 55],
     [48, 49, 50, 51, 52, 54],
     [52, 53],
     [48, 49, 53, 54, 55],
     [48, 49, 52, 55],
     [48, 49, 51, 52, 55],
     [58, 59],
     [56, 61, 63],
     [57, 63],
     [56, 59, 60],
     [61, 63],
     [57, 58, 61, 62, 63],
     [57, 58],
     [60, 62]]

def enc(v, keys, le):
    t = v
    for i in keys:
        q = []
        for j in P:
            tmp = z3.BitVecVal(0,1)
            for k in j:
                tmp ^= t[k]
            q.append(tmp)
        t = [q[j] ^ i[j] for j in range(le)]
    return t

from Crypto.Util.number import *
from z3 import *
key_sym = [[z3.BitVec("key_%d_%d" % (j,i), 1) for i in range(64)] for j in range(3)]
plain_sym =[[z3.BitVec("plain_%d_%d" % (j,i), 1) for i in range(64)] for j in range(8)]
sol = z3.Solver()

c = "11101100100000110101100101100001100111011100100111000000010110000110011011000100110101110111010000100100001100010011001100010100101000110001011101000000100010101000000110000110011110001101110110110111000000100010011011011011101011101000000000100010000101001110100101011000001110010000000000100110001101110011111010001100101101111010101111101110100110101010011010011010101110100001001101100110010000010000011100100101111010010000011001000110000100110111100010101011000100100111010000101010110110001010110101111111"

for i in range(48):
    sol.add(plain_sym[0][i] == 0)

for _ in range(8):
    a = enc(plain_sym[_], key_sym, 64)

    for i in range(64):
        sol.add(a[i] == c[_*64+i])


plains_sym =[[z3.BitVec("plains_%d_%d" % (i,j), 8) for i in range(8)] for j in range(8)]

for i in range(8):
    for j in range(8):
        for k in range(8):
            sol.add(plain_sym[i][8*j+k] == Extract(7-k, 7-k, plains_sym[i][j]))


for j in range(6):
    sol.add(0==plains_sym[0][j])
sol.add(125==plains_sym[-1][-1])

for i in range(1,8):
    for j in range(8):
        sol.add(Or(And(48<=plains_sym[i][j],plains_sym[i][j] <= 57) , And(95<=plains_sym[i][j])) )

if sol.check() == sat:
    m = sol.model()
    
    flag = ""
    for i in range(0,8):
        a = [m.eval(x).as_long() for x in plains_sym[i]]
        flag += '' .join (chr(i) for i in a)
    print(flag)

# flag{flag_is_the_readable_key_whose_md5_starts_with_3fe04}

然后发现原来我们需要恢复 key，那就继续 z3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from Crypto.Util.number import *
from z3 import *
from recover import P

def enc(v, keys, le):
    t = v
    for i in keys:
        q = []
        for j in P:
            tmp = z3.BitVecVal(0,1)
            for k in j:
                tmp ^= t[k]
            q.append(tmp)
        t = [q[j] ^ i[j] for j in range(le)]
    return t

c = "11101100100000110101100101100001100111011100100111000000010110000110011011000100110101110111010000100100001100010011001100010100101000110001011101000000100010101000000110000110011110001101110110110111000000100010011011011011101011101000000000100010000101001110100101011000001110010000000000100110001101110011111010001100101101111010101111101110100110101010011010011010101110100001001101100110010000010000011100100101111010010000011001000110000100110111100010101011000100100111010000101010110110001010110101111111"
p = '00000000000000000000000000000000000000000000000001100110011011000110000101100111011110110110011001101100011000010110011101011111011010010111001101011111011101000110100001100101010111110111001001100101011000010110010001100001011000100110110001100101010111110110101101100101011110010101111101110111011010000110111101110011011001010101111101101101011001000011010101011111011100110111010001100001011100100111010001110011010111110111011101101001011101000110100001011111001100110110011001100101001100000011010001111101'

c = [int(i) for i in list(c)]
p = [int(i) for i in list(p)]

key_sym = [[z3.BitVec("key_%d_%d" % (j,i), 1) for i in range(64)] for j in range(3)]
keys_sym = [[z3.BitVec("key_%d_%d" % (j,i), 8) for i in range(8)] for j in range(3)]

sol = z3.Solver()

# 约束 key 全部为小写字母
for i in range(3):
    for j in range(8):
        for k in range(8):
            sol.add(key_sym[i][8*j+k] == Extract(7-k, 7-k, keys_sym[i][j]))

for i in range(5,23):	
    sol.add(And(97<=keys_sym[i//8][i%8],keys_sym[i//8][i%8]<=122))

# 约束flag格式
sol.add(keys_sym[0][0]== ord('f'))
sol.add(keys_sym[0][1]== ord('l'))
sol.add(keys_sym[0][2]== ord('a'))
sol.add(keys_sym[0][3]== ord('g'))
sol.add(keys_sym[0][4]== ord('{'))
sol.add(keys_sym[2][7]== ord('}'))

# 基础约束：明文使用密钥加密后为指定密文
for i in range(8):
    a = enc(p[i*64:i*64+64], key_sym, 64)
    for j in range(64):
        sol.add(a[j] == c[i*64+j])

        
if sol.check() == sat:
    m = sol.model()
    key = ''
    for i in range(3):
        a = [m.eval(x).as_long() for x in keys_sym[i]]
        key += ''.join(chr(i) for i in a)

    key = key.encode()
    print("[+]",key)

随后发现有多解了，而 z3 又无法给出所有的解，于是我就开始猜了。

猜key中包含哪些字符，首先根据题目名，我猜回包含字符串 recover，但不确定 recover 的位置，那就爆 ！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from z3 import *
from hashlib import md5
from recover import P

def MD5(x): return md5(x).hexdigest()

def enc(v, keys, le):
    t = v
    for i in keys:
        q = []
        for j in P:
            tmp = z3.BitVecVal(0,1)
            for k in j:
                tmp ^= t[k]
            q.append(tmp)
        t = [q[j] ^ i[j] for j in range(le)]
    return t

from Crypto.Util.number import *

c = "11101100100000110101100101100001100111011100100111000000010110000110011011000100110101110111010000100100001100010011001100010100101000110001011101000000100010101000000110000110011110001101110110110111000000100010011011011011101011101000000000100010000101001110100101011000001110010000000000100110001101110011111010001100101101111010101111101110100110101010011010011010101110100001001101100110010000010000011100100101111010010000011001000110000100110111100010101011000100100111010000101010110110001010110101111111"
p = '00000000000000000000000000000000000000000000000001100110011011000110000101100111011110110110011001101100011000010110011101011111011010010111001101011111011101000110100001100101010111110111001001100101011000010110010001100001011000100110110001100101010111110110101101100101011110010101111101110111011010000110111101110011011001010101111101101101011001000011010101011111011100110111010001100001011100100111010001110011010111110111011101101001011101000110100001011111001100110110011001100101001100000011010001111101'

def attack2(index):
    key_sym = [[z3.BitVec("key_%d_%d" % (j,i), 1) for i in range(64)] for j in range(3)]
    keys_sym = [[z3.BitVec("key_%d_%d" % (j,i), 8) for i in range(8)] for j in range(3)]

    sol = z3.Solver()

    for i in range(3):
        for j in range(8):
            for k in range(8):
                sol.add(key_sym[i][8*j+k] == Extract(7-k, 7-k, keys_sym[i][j]))

    for i in range(5,23):
        sol.add(And(97<=keys_sym[i//8][i%8],keys_sym[i//8][i%8]<=122))

    sol.add(keys_sym[0][0]== ord('f'))
    sol.add(keys_sym[0][1]== ord('l'))
    sol.add(keys_sym[0][2]== ord('a'))
    sol.add(keys_sym[0][3]== ord('g'))
    sol.add(keys_sym[0][4]== ord('{'))
    sol.add(keys_sym[2][7]== ord('}'))


    sol.add(keys_sym[(index+0)//8][(index+0)%8]== ord('r'))
    sol.add(keys_sym[(index+1)//8][(index+1)%8]== ord('e'))
    sol.add(keys_sym[(index+2)//8][(index+2)%8]== ord('c'))
    sol.add(keys_sym[(index+3)//8][(index+3)%8]== ord('o'))
    sol.add(keys_sym[(index+4)//8][(index+4)%8]== ord('v'))
    sol.add(keys_sym[(index+5)//8][(index+5)%8]== ord('e'))
    sol.add(keys_sym[(index+6)//8][(index+6)%8]== ord('r'))
    



    for i in range(8):
        a = enc(p[i*64:i*64+64], key_sym, 64)
        for j in range(64):
            sol.add(a[j] == c[i*64+j])

    if sol.check() == sat:
        m = sol.model()

        key = ''
        for i in range(3):
            a = [m.eval(x).as_long() for x in keys_sym[i]]
            key += ''.join(chr(i) for i in a)

        key = key.encode()
        print(key)
        if MD5(key)[:5] == '3fe04':
            print("[+]",key)
            exit()

from tqdm import *
table = "qwertyuiopasdfghjklzxcvbnm"
for index in range(0,24-6):
    attack2(index)

得到 b'flag{ynrdertqrecoveryoe}'，还不是正确答案，不过看到 recover 的位置，最后还剩 3 个字节，而且还有一个 e 在最后，忙猜是一个 key，于是再加三条约束

1
2
3
sol.add(keys_sym[2][4]== ord('k'))
sol.add(keys_sym[2][5]== ord('e'))
sol.add(keys_sym[2][6]== ord('y'))

跑一下脚本，bingo！

1
2
b'flag{hardertorecoverkey}'
[+] b'flag{hardertorecoverkey}'

估摸着出题人的预期应该不是这么做，可以赛后看一下官方 wp 学习一下。

SecureAgg

交互题，看到 handle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def handle(self):
    signal.alarm(180)

    self.send(BANNER)
    self.send(b"Generating parameters...")
    agg=AggServer(114)
    agg.genKeys()
    self.send(agg.system_info().encode())

    try:
        for i in range(ROUNDS):
            self.send(f'#Round {i+1}'.encode())
            enc_list=agg.get_enc_list()
            self.send(f"enc_list={enc_list}".encode())
            key=agg.aggregate()
            message=''.join(random.sample(string.ascii_letters,16))
            aes_key=sha256(str(key).encode()).digest()[:16]
            aes=AES.new(aes_key,AES.MODE_CBC,iv=bytes(range(16)))
            enc=aes.encrypt(pad(message.encode(),16))
            self.send(f"enc={b64encode(enc)}".encode())
            inp=self.recv(b"input your message: ").decode()
            if inp==message:
                self.send(b'Correct!')
            else:
                self.send(b'Error!')
                exit(0)
            agg.update()
        self.send(flag)
    except:
        self.send(b'wtf?')
    self.close()

看一下题目流程，一共二十轮，每一轮

  1. 题目会给出一个 enc_list，

  2. 然后使用 agg.aggregate() 生成一个密钥 key

  3. 下面会用这个 key 作为 AES 密钥加密一段随机字符串，要求我们解密这个随机字符串

轮与轮之间都是相互独立的，没啥操作空间，就是很单纯的要根据 enc_list 来恢复 key

定位到 enc_list 和 key 相关的代码，在AggServer.py

1
2
3
4
5
6
7
8
9
10
11
def get_enc_list(self):
    enc_list=[]
    for u in self.users:
        enc_data=u.get_enc_data(self.M)
        enc_list.append(enc_data)
    return enc_list
...

def aggregate(self):
    self.key=sum([ u.data for u in self.users])%self.M
    return self.key

所以 enc_list 就是每个用户的 enc_data 组成列表，key 就是每个用户的 data 之和。

我们继续看到 enc_data 相关的代码，在User.py

1
2
3
4
5
6
7
8
def get_enc_data(self,M):
    enc=(114*self.data+514)%M
    for id,k in self.agreement_keys.items():
        if id>self.id:
            enc+=PRG(k).randbits(self.mbits)%M
        elif id<self.id:
            enc-=PRG(k).randbits(self.mbits)%M
    return enc

其中 PRG 就是一个 LCG 伪随机数生成器，k 就是每个用户的自己的私钥和其他用户公钥生成的类似 DH 交换密钥的值 

1
2
3
4
5
6
7
def agree(self,users,p):
    self.agreement_keys={}
    for u in users:
        if u.id!=self.id:
            u_pub=u.pub
            k=pow(u_pub,self.priv,p)
            self.agreement_keys.update({u.id:k})

id 是每个用户的id值（0-7）。所以思路来了：将 enc_data 求和减去 514*8 ，再在模 M 下除以 114 就可以了

举个例子， 在 get_enc_data 中有用户 A 和 B，A 的 id 小于 B，所以 A 的 enc 会减一个 $PRG((g^{b})^a)$，但是 B 的 id 大约 A，所以 B 的 enc 会加一个 $PRG((g^a)^b)$，是相等的，所以全加在一起的话就都消掉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad
from base64 import b64encode,b64decode

context.log_level = 'debug'

def dec(c,key):
    aes_key=sha256(str(key).encode()).digest()[:16]
    aes=AES.new(aes_key,AES.MODE_CBC,iv=bytes(range(16)))
    message=unpad(aes.decrypt(b64decode(c)))
    return message



sh = remote("nepctf.1cepeak.cn",31045)
sh.recvutil("M=")
M = int(sh.recvutil("\n")[:-1])
for _ in range(20):
    sh.recvutil("enc_list=")
    pubkeys = eval(sh.recvutil("]"))
    sh.recvutil("enc=b'")
    c = sh.recvutil("'")[:-1]
    key = (sum(pubkeys)-514*8)*inverse(114,M) % M
    sh.recvutil("input your message: ")

    sh.sendline(dec(c,key))
sh.interactive()

simple_des

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
from operator import add
from typing import List
from functools import reduce
from gmpy2 import *
from Crypto.Util.number import *


_IP = [57, 49, 41, 33, 25, 17, 9,  1,
	59, 51, 43, 35, 27, 19, 11, 3,
	61, 53, 45, 37, 29, 21, 13, 5,
	63, 55, 47, 39, 31, 23, 15, 7,
	56, 48, 40, 32, 24, 16, 8,  0,
	58, 50, 42, 34, 26, 18, 10, 2,
	60, 52, 44, 36, 28, 20, 12, 4,
	62, 54, 46, 38, 30, 22, 14, 6
]

def IP(plain: List[int]) -> List[int]:
    return [plain[x] for x in _IP]

__pc1 = [56, 48, 40, 32, 24, 16,  8,
	  0, 57, 49, 41, 33, 25, 17,
	  9,  1, 58, 50, 42, 34, 26,
	 18, 10,  2, 59, 51, 43, 35,
	 62, 54, 46, 38, 30, 22, 14,
	  6, 61, 53, 45, 37, 29, 21,
	 13,  5, 60, 52, 44, 36, 28,
	 20, 12,  4, 27, 19, 11,  3
]

__pc2 = [
	13, 16, 10, 23,  0,  4,
	 2, 27, 14,  5, 20,  9,
	22, 18, 11,  3, 25,  7,
	15,  6, 26, 19, 12,  1,
	40, 51, 30, 36, 46, 54,
	29, 39, 50, 44, 32, 47,
	43, 48, 38, 55, 33, 52,
	45, 41, 49, 35, 28, 31
]
ROTATIONS = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

def PC_1(key: List[int]) -> List[int]:
    return [key[x] for x in __pc1]

def PC_2(key: List[int]) -> List[int]:
    return [key[x] for x in __pc2]

def get_sub_key(key: List[int]) -> List[List[int]]:
    key = PC_1(key)
    L, R = key[:28], key[28:]

    sub_keys = []

    for i in range(16):
        for j in range(ROTATIONS[i]):
            L.append(L.pop(0))
            R.append(R.pop(0))

        combined = L + R
        if i == 0:
        	print(f"combined = {combined}")
        sub_key = PC_2(combined)
        sub_keys.append(sub_key)
    print('LL=',L)
    print('Rr=',R)
    return sub_keys

__ep = [31,  0,  1,  2,  3,  4,
		 3,  4,  5,  6,  7,  8,
		 7,  8,  9, 10, 11, 12,
		11, 12, 13, 14, 15, 16,
		15, 16, 17, 18, 19, 20,
		19, 20, 21, 22, 23, 24,
		23, 24, 25, 26, 27, 28,
		27, 28, 29, 30, 31,  0
]

__p = [15,  6, 19, 20, 28, 11, 27, 16,
		0, 14, 22, 25,  4, 17, 30,  9,
		1,  7, 23, 13, 31, 26,  2,  8,
		18, 12, 29,  5, 21, 10,  3, 24
]

def EP(data: List[int]) -> List[int]:
    return [data[x] for x in __ep]

def P(data: List[int]) -> List[int]:
    return [data[x] for x in __p]

__s_box = [

	[
		[14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7],
		[ 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8],
		[ 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0],
		[15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13]
	],


	[
		[15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10],
		[ 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5],
		[ 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15],
		[13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9]
	],


	[
		[10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8],
		[13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1],
		[13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7],
		[ 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12]
	],


	[
		[ 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15],
		[13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9],
		[10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4],
		[ 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14]
	],


	[
		[ 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9],
		[14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6],
		[ 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14],
		[11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3]
	],


	[
		[12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11],
		[10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8],
		[ 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6],
		[ 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13]
	],


	[
		[ 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1],
		[13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6],
		[ 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2],
		[ 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12]
	],


	[
		[13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7],
		[ 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2],
		[ 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8],
		[ 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11]
	]
]

def S_box(data: List[int]) -> List[int]:
    output = []
    for i in range(0, 48, 6):
        row = data[i] * 2 + data[i + 5]
        col = reduce(add, [data[i + j] * (2 ** (4 - j)) for j in range(1, 5)])
        output += [int(x) for x in format(__s_box[i // 6][row][col], '04b')]
    return output

def encrypt(plain: List[int], sub_keys: List[List[int]]) -> List[int]:
    plain = IP(plain)
    L, R = plain[:32], plain[32:]

    for i in range(16):
        prev_L = L
        L = R
        expanded_R = EP(R)
        xor_result = [a ^ b for a, b in zip(expanded_R, sub_keys[i])]
        substituted = S_box(xor_result)
        permuted = P(substituted)

        R = [a ^ b for a, b in zip(permuted, prev_L)]

    cipher = R + L
    cipher = [cipher[x] for x in [39,  7, 47, 15, 55, 23, 63, 31,
                                38,  6, 46, 14, 54, 22, 62, 30,
                                37,  5, 45, 13, 53, 21, 61, 29,
                                36,  4, 44, 12, 52, 20, 60, 28,
                                35,  3, 43, 11, 51, 19, 59, 27,
                                34,  2, 42, 10, 50, 18, 58, 26,
                                33,  1, 41,  9, 49, 17, 57, 25,
                                32,  0, 40,  8, 48, 16, 56, 24]]

    return cipher


def bitxor(plain1: List[int], plain2: List[List[int]]) -> List[int]:
    return [int(i) for i in bin(int(''.join(str(i) for i in plain1),2)^int(''.join(str(i) for i in plain2),2))[2:].zfill(64)]

#key的字母表为abcdefghijklmnopqrstuvwsyz
from secret import flag, key

t=[]
z=[[0]*64]
from operator import add
key = reduce(add, [list(map(int, bin(key_byte)[2:].zfill(8))) for key_byte in key])
for i in range(0,3):
    pt = reduce(add, [list(map(int, bin(flag_byte)[2:].zfill(8))) for flag_byte in flag[ 8*i:8*(i+1) ]])
    ct = encrypt(pt, get_sub_key(bitxor(z[i],key)))
    z.append(pt)
    t += ct
print(t)


'''
i=0情况下的LL,Rr
LL= [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Rr= [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0]
t=[0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0]
'''

题目实现了一个经典的 DES ，不过除了第一组，后面两组加密时密钥会先和前一组的明文异或。题目还给出了第一组加密时的最后一轮轮密钥（ L 部分少了 9 比特，可以爆）

拿出当初祥哥的板子 https://blog.soreatu.com/posts/intended-solution-to-crypto-problems-in-nctf-2019/#reverse909pt-2solvers ，爆一下 L 少的 9 比特就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from base64 import b64decode
from itertools import product
from DES import * 			 # https://github.com/soreatu/Cryptography/blob/master/DES.py
from typing import List

guess_8bit = list(product(range(2), repeat=8))
not_in_PC2 = [9,18,22,25,35,38,43,54]

def re_PC2(sbkey):
    # 48-bit -> 56-bit
    res = [0]*56
    for i in range(len(sbkey)):
        res[PC_2_table[i]-1] = sbkey[i]
    return res # ok

def guess_CiDi10(sbkey, t):
    res = re_PC2(sbkey)
    for i in range(8):
        res[not_in_PC2[i]-1] = guess_8bit[t][i]
    return res # ok

def guess_allsbkey(roundkey, r, t):
    sbkey = [[]]*16
    sbkey[r] = roundkey
    CiDi = guess_CiDi10(roundkey, t)
    Ci, Di = CiDi[:28], CiDi[28:]
    for i in range(r+1,r+16):
        Ci, Di = LR(Ci, Di, i%16)
        sbkey[i%16] = PC_2(Ci+Di)
        if i%16 == 0:
            combined = Ci+Di
    return combined,sbkey # ok

def long_des_enc(c, k):
    assert len(c) % 8 == 0
    res = b''
    for i in range(0,len(c),8):
        res += DES_enc(c[i:i+8], k)
    return res

def try_des(cipher, roundkey):
    for t in range(256):
        combined,allkey = guess_allsbkey(roundkey, 15, t)
        plain = long_des_enc(cipher, allkey[::-1])
        if plain.startswith(b'Nep'):
            print(combined,plain)
            exit()

def PC_2(key: List[int]) -> List[int]:
    return [key[x] for x in __pc2]

__pc2 = [
    13, 16, 10, 23,  0,  4,
     2, 27, 14,  5, 20,  9,
    22, 18, 11,  3, 25,  7,
    15,  6, 26, 19, 12,  1,
    40, 51, 30, 36, 46, 54,
    29, 39, 50, 44, 32, 47,
    43, 48, 38, 55, 33, 52,
    45, 41, 49, 35, 28, 31
]

from Crypto.Util.number import *


tt=[0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0]
t = tt[:64]
t = ''.join(str(i) for i in t)
t= int(t,2)
t = long_to_bytes(t)

LL= [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Rr= [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0]
from tqdm import *
for i in range(2**9-1,2**7,-1):
    tmp =  list(bin(i)[2:].rjust(9,'0'))
    L = LL + [ int(u) for u in tmp]
    R = Rr
    combined = L+R
    sub_key = PC_2(combined)
    try_des(t, sub_key)

# [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0] b'NepCTF{N'

得到第一组明文：NepCTF{N，顺便输出了第一轮的轮密钥 combined。

然后拿着第一组的明文 NepCTF{N，做一个密钥拓展那边的 PC_1 置换，再左右两边各自向左循环移位一下，再异或输出的第一轮的轮密钥 combined，就可以解密第二组密文了，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from functools import reduce
from operator import add


from Crypto.Util.number import *

def attack(p,c):
    combined = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0]

    p = bin(p)[2:].rjust(64,'0')
    p = [int(i) for i in p]
	
    # 对明文 PC_1 置换
    P = PC_1(p)
    
    # 对明文左右两部分进行第一轮的循环移位
    
    Ci, Di = LR(P[:28], P[28:], 0)
    P = Ci+Di
    CiDi = []
    for i in range(56):
        CiDi.append(P[i]^combined[i])
	
    # 生成所有轮密钥
    Ci, Di = CiDi[:28], CiDi[28:]
    sbkey = [[]]*16
    sbkey[0] = PC_2(Ci+Di)

    r = 1
    for i in range(r,r+16):
        Ci, Di = LR(Ci, Di, i%16)
        sbkey[i%16] = PC_2(Ci+Di)

	# 解密密文
    c = ''.join(str(i) for i in c)
    c= int(c,2)
    c = long_to_bytes(c)
    return long_des_enc(c, sbkey[::-1])


tt=[0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0]
flag = b"NepCTF{N"
for i in range(2):
    t = tt[64*i+64:64*i+128]
    p = flag[i*8:i*8+8]
    flag += attack(bytes_to_long(p),t)
print(flag)

# b'NepCTF{Nep_d0wn_ddddd1s}'
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com

赏

文章标题:2023 NepCTF

文章字数:8.3k

本文作者:Van1sh

发布时间:2023-08-14, 12:00:00

最后更新:2023-08-14, 20:45:14

原始链接:http://jayxv.github.io/2023/08/14/2023 NepCTF/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2020 Van1sh

Built with Hexo and 3-hexo theme

目录
×

喜欢就点赞,疼爱就打赏